/*
 (c) 2013, Vladimir Agafonkin
 RBush, a JavaScript library for high-performance 2D spatial indexing of points and rectangles.
 https://github.com/mourner/rbush
 */

(function () {
    'use strict';

    function rbush(maxEntries, format) {

        // jshint newcap: false, validthis: true
        if (!(this instanceof rbush)) {
            return new rbush(maxEntries, format);
        }

        // max entries in a node is 9 by default; min node fill is 40% for best performance
        this._maxEntries = Math.max(4, maxEntries || 9);
        this._minEntries = Math.max(2, Math.ceil(this._maxEntries * 0.4));

        if (format) {
            this._initFormat(format);
        }

        this.clear();
    }

    rbush.prototype = {

        all: function () {
            return this._all(this.data, []);
        },

        search: function (bbox) {

            var node = this.data,
                result = [];

            if (!this._intersects(bbox, node.bbox)) {
                return result;
            }

            var nodesToSearch = [],
                i, len, child, childBBox;

            while (node) {
                for (i = 0, len = node.children.length; i < len; i++) {
                    child = node.children[i];
                    childBBox = node.leaf ? this.toBBox(child) : child.bbox;

                    if (this._intersects(bbox, childBBox)) {

                        if (node.leaf) {
                            result.push(child);

                        } else if (this._contains(bbox, childBBox)) {
                            this._all(child, result);

                        } else {
                            nodesToSearch.push(child);
                        }
                    }
                }

                node = nodesToSearch.pop();
            }

            return result;
        },

        load: function (data) {
            if (!(data && data.length)) {
                return this;
            }

            if (data.length < this._minEntries) {
                for (var i = 0, len = data.length; i < len; i++) {
                    this.insert(data[i]);
                }
                return this;
            }

            // recursively build the tree with the given data from stratch using OMT algorithm
            var node = this._build(data.slice(), 0);

            if (!this.data.children.length) {
                // save as is if tree is empty
                this.data = node;

            } else if (this.data.height === node.height) {
                // split root if trees have the same height
                this._splitRoot(this.data, node);

            } else {
                if (this.data.height < node.height) {
                    // swap trees if inserted one is bigger
                    var tmpNode = this.data;
                    this.data = node;
                    node = tmpNode;
                }

                // insert the small tree into the large tree at appropriate level
                this._insert(node, this.data.height - node.height - 1, true);
            }

            return this;
        },

        insert: function (item) {
            if (item) {
                this._insert(item, this.data.height - 1);
            }
            return this;
        },

        clear: function () {
            this.data = {
                children: [],
                leaf: true,
                bbox: this._empty(),
                height: 1
            };
            return this;
        },

        remove: function (item) {
            if (!item) {
                return this;
            }

            var node = this.data,
                bbox = this.toBBox(item),
                path = [],
                indexes = [],
                i, parent, index, goingUp;

            // depth-first iterative tree traversal
            while (node || path.length) {

                if (!node) { // go up
                    node = path.pop();
                    parent = path[path.length - 1];
                    i = indexes.pop();
                    goingUp = true;
                }

                if (node.leaf) { // check current node
                    index = node.children.indexOf(item);

                    if (index !== -1) {
                        // item found, remove the item and condense tree upwards
                        node.children.splice(index, 1);
                        path.push(node);
                        this._condense(path);
                        return this;
                    }
                }

                if (!goingUp && !node.leaf && this._contains(node.bbox, bbox)) { // go down
                    path.push(node);
                    indexes.push(i);
                    i = 0;
                    parent = node;
                    node = node.children[0];

                } else if (parent) { // go right
                    i++;
                    node = parent.children[i];
                    goingUp = false;

                } else { // nothing found
                    node = null;
                }
            }

            return this;
        },

        toBBox: function (item) {
            return item;
        },

        compareMinX: function (a, b) {
            return a[0] - b[0];
        },
        compareMinY: function (a, b) {
            return a[1] - b[1];
        },

        toJSON: function () {
            return this.data;
        },

        fromJSON: function (data) {
            this.data = data;
            return this;
        },

        _all: function (node, result) {
            var nodesToSearch = [];
            while (node) {
                if (node.leaf) {
                    result.push.apply(result, node.children);
                } else {
                    nodesToSearch.push.apply(nodesToSearch, node.children);
                }
                node = nodesToSearch.pop();
            }
            return result;
        },

        _build: function (items, level, height) {

            var N = items.length,
                M = this._maxEntries,
                node;

            if (N <= M) {
                node = {
                    children: items,
                    leaf: true,
                    height: 1
                };
                this._calcBBox(node);
                return node;
            }

            if (!level) {
                // target height of the bulk-loaded tree
                height = Math.ceil(Math.log(N) / Math.log(M));

                // target number of root entries to maximize storage utilization
                M = Math.ceil(N / Math.pow(M, height - 1));

                items.sort(this.compareMinX);
            }

            // TODO eliminate recursion?

            node = {
                children: [],
                height: height
            };

            var N1 = Math.ceil(N / M) * Math.ceil(Math.sqrt(M)),
                N2 = Math.ceil(N / M),
                compare = level % 2 === 1 ? this.compareMinX : this.compareMinY,
                i, j, slice, sliceLen, childNode;

            // split the items into M mostly square tiles
            for (i = 0; i < N; i += N1) {
                slice = items.slice(i, i + N1).sort(compare);

                for (j = 0, sliceLen = slice.length; j < sliceLen; j += N2) {
                    // pack each entry recursively
                    childNode = this._build(slice.slice(j, j + N2), level + 1, height - 1);
                    node.children.push(childNode);
                }
            }

            this._calcBBox(node);

            return node;
        },

        _chooseSubtree: function (bbox, node, level, path) {

            var i, len, child, targetNode, area, enlargement, minArea, minEnlargement;

            while (true) {
                path.push(node);

                if (node.leaf || path.length - 1 === level) {
                    break;
                }

                minArea = minEnlargement = Infinity;

                for (i = 0, len = node.children.length; i < len; i++) {
                    child = node.children[i];
                    area = this._area(child.bbox);
                    enlargement = this._enlargedArea(bbox, child.bbox) - area;

                    // choose entry with the least area enlargement
                    if (enlargement < minEnlargement) {
                        minEnlargement = enlargement;
                        minArea = area < minArea ? area : minArea;
                        targetNode = child;

                    } else if (enlargement === minEnlargement) {
                        // otherwise choose one with the smallest area
                        if (area < minArea) {
                            minArea = area;
                            targetNode = child;
                        }
                    }
                }

                node = targetNode;
            }

            return node;
        },

        _insert: function (item, level, isNode) {

            var bbox = isNode ? item.bbox : this.toBBox(item),
                insertPath = [];

            // find the best node for accommodating the item, saving all nodes along the path too
            var node = this._chooseSubtree(bbox, this.data, level, insertPath);

            // put the item into the node
            node.children.push(item);
            this._extend(node.bbox, bbox);

            // split on node overflow; propagate upwards if necessary
            while (level >= 0) {
                if (insertPath[level].children.length > this._maxEntries) {
                    this._split(insertPath, level);
                    level--;
                } else {
                    break;
                }
            }

            // adjust bboxes along the insertion path
            this._adjustParentBBoxes(bbox, insertPath, level);
        },

        // split overflowed node into two
        _split: function (insertPath, level) {

            var node = insertPath[level],
                M = node.children.length,
                m = this._minEntries;

            this._chooseSplitAxis(node, m, M);

            var newNode = {
                children: node.children.splice(this._chooseSplitIndex(node, m, M)),
                height: node.height
            };

            if (node.leaf) {
                newNode.leaf = true;
            }

            this._calcBBox(node);
            this._calcBBox(newNode);

            if (level) {
                insertPath[level - 1].children.push(newNode);
            } else {
                this._splitRoot(node, newNode);
            }
        },

        _splitRoot: function (node, newNode) {
            // split root node
            this.data = {};
            this.data.children = [node, newNode];
            this.data.height = node.height + 1;
            this._calcBBox(this.data);
        },

        _chooseSplitIndex: function (node, m, M) {

            var i, bbox1, bbox2, overlap, area, minOverlap, minArea, index;

            minOverlap = minArea = Infinity;

            for (i = m; i <= M - m; i++) {
                bbox1 = this._distBBox(node, 0, i);
                bbox2 = this._distBBox(node, i, M);

                overlap = this._intersectionArea(bbox1, bbox2);
                area = this._area(bbox1) + this._area(bbox2);

                // choose distribution with minimum overlap
                if (overlap < minOverlap) {
                    minOverlap = overlap;
                    index = i;

                    minArea = area < minArea ? area : minArea;

                } else if (overlap === minOverlap) {
                    // otherwise choose distribution with minimum area
                    if (area < minArea) {
                        minArea = area;
                        index = i;
                    }
                }
            }

            return index;
        },

        // sorts node children by the best axis for split
        _chooseSplitAxis: function (node, m, M) {

            var compareMinX = node.leaf ? this.compareMinX : this._compareNodeMinX,
                compareMinY = node.leaf ? this.compareMinY : this._compareNodeMinY,
                xMargin = this._allDistMargin(node, m, M, compareMinX),
                yMargin = this._allDistMargin(node, m, M, compareMinY);

            // if total distributions margin value is minimal for x, sort by minX,
            // otherwise it's already sorted by minY

            if (xMargin < yMargin) {
                node.children.sort(compareMinX);
            }
        },

        // total margin of all possible split distributions where each node is at least m full
        _allDistMargin: function (node, m, M, compare) {

            node.children.sort(compare);

            var leftBBox = this._distBBox(node, 0, m),
                rightBBox = this._distBBox(node, M - m, M),
                margin = this._margin(leftBBox) + this._margin(rightBBox),
                i, child;

            for (i = m; i < M - m; i++) {
                child = node.children[i];
                this._extend(leftBBox, node.leaf ? this.toBBox(child) : child.bbox);
                margin += this._margin(leftBBox);
            }

            for (i = M - m - 1; i >= m; i--) {
                child = node.children[i];
                this._extend(rightBBox, node.leaf ? this.toBBox(child) : child.bbox);
                margin += this._margin(rightBBox);
            }

            return margin;
        },

        // min bounding rectangle of node children from k to p-1
        _distBBox: function (node, k, p) {
            var bbox = this._empty();

            for (var i = k, child; i < p; i++) {
                child = node.children[i];
                this._extend(bbox, node.leaf ? this.toBBox(child) : child.bbox);
            }

            return bbox;
        },

        // calculate node's bbox from bboxes of its children
        _calcBBox: function (node) {
            node.bbox = this._distBBox(node, 0, node.children.length);
        },

        _adjustParentBBoxes: function (bbox, path, level) {
            // adjust bboxes along the given tree path
            for (var i = level; i >= 0; i--) {
                this._extend(path[i].bbox, bbox);
            }
        },

        _condense: function (path) {
            // go through the path, removing empty nodes and updating bboxes
            for (var i = path.length - 1, siblings; i >= 0; i--) {
                if (path[i].children.length === 0) {
                    if (i > 0) {
                        siblings = path[i - 1].children;
                        siblings.splice(siblings.indexOf(path[i]), 1);
                    } else {
                        this.clear();
                    }
                } else {
                    this._calcBBox(path[i]);
                }
            }
        },

        _contains: function (a, b) {
            return a[0] <= b[0] &&
                a[1] <= b[1] &&
                b[2] <= a[2] &&
                b[3] <= a[3];
        },

        _intersects: function (a, b) {
            return b[0] <= a[2] &&
                b[1] <= a[3] &&
                b[2] >= a[0] &&
                b[3] >= a[1];
        },

        _extend: function (a, b) {
            a[0] = Math.min(a[0], b[0]);
            a[1] = Math.min(a[1], b[1]);
            a[2] = Math.max(a[2], b[2]);
            a[3] = Math.max(a[3], b[3]);
            return a;
        },

        _area: function (a) {
            return (a[2] - a[0]) * (a[3] - a[1]);
        },
        _margin: function (a) {
            return (a[2] - a[0]) + (a[3] - a[1]);
        },

        _enlargedArea: function (a, b) {
            return (Math.max(b[2], a[2]) - Math.min(b[0], a[0])) *
                (Math.max(b[3], a[3]) - Math.min(b[1], a[1]));
        },

        _intersectionArea: function (a, b) {
            var minX = Math.max(a[0], b[0]),
                minY = Math.max(a[1], b[1]),
                maxX = Math.min(a[2], b[2]),
                maxY = Math.min(a[3], b[3]);

            return Math.max(0, maxX - minX) *
                Math.max(0, maxY - minY);
        },

        _empty: function () {
            return [Infinity, Infinity, -Infinity, -Infinity];
        },

        _compareNodeMinX: function (a, b) {
            return a.bbox[0] - b.bbox[0];
        },
        _compareNodeMinY: function (a, b) {
            return a.bbox[1] - b.bbox[1];
        },

        _initFormat: function (format) {
            // data format (minX, minY, maxX, maxY accessors)

            // uses eval-type function compilation instead of just accepting a toBBox function
            // because the algorithms are very sensitive to sorting functions performance,
            // so they should be dead simple and without inner calls

            // jshint evil: true

            var compareArr = ['return a', ' - b', ';'];

            this.compareMinX = new Function('a', 'b', compareArr.join(format[0]));
            this.compareMinY = new Function('a', 'b', compareArr.join(format[1]));

            this.toBBox = new Function('a', 'return [a' + format.join(', a') + '];');
        }
    };

    if (typeof define === 'function' && define.amd) {
        define(function () {
            return rbush;
        });
    } else if (typeof module !== 'undefined') {
        module.exports = rbush;
    } else if (typeof self !== 'undefined') {
        self.rbush = rbush;
    } else {
        window.rbush = rbush;
    }

})();